Caching is a technique used ubiquitously in modern data processing systems. It is often used to reduce bandwidth usage between a user and a primary storage facility, to reduce load on a server or memory device, and for other purposes. In certain applications, multiple caching devices may have the ability to handle modifications to the same data. This scenario gives rise to the problem of maintaining “cache coherency”. Cache coherency refers to the consistency of data stored in one or more caches of multiple caches that share a data resource.
Cache coherency problems can arise, for example, when read-modify-write operations are used by buffer caches to modify data. A “buffer cache” is a caching device used to temporarily store data read from or written to a persistent primary storage facility that contains the master copy of the data. A network storage server can be employed as a buffer cache between an origin server and a user. As another example, within a network storage server, random access memory can be employed as a buffer cache to cache data stored persistently in a set of mass storage devices, such as disks.
Most buffer caches are designed to cache only whole blocks of storage, since the storage devices commonly used today for persistent storage, such as disks, only allow reading and writing of whole blocks. Therefore, to support the modification of just one part of a block that is not currently in the cache, a buffer cache conventionally implements a technique known as “read-modify-write”. In this technique, the buffer cache first reads the block from an origin server into the cache, then modifies the specified portion of the block, and then sends the modified copy of the entire block back to the origin server. However, if two different buffer caches attempt to do this to the same block at the same time, data errors can result.
For example, suppose two network clients, client A and client B, that each function as a buffer cache both read the same data block from an origin server. Then client A modifies the first three bytes of its copy of the block and sends the whole block back to the origin server, which writes it to disk. Then client B modifies the last five bytes of its copy of the block and sends the whole block back to the server. The server than overwrites the block on disk again with this new version. However, client B's version does not have the changes made by client A, so client A's changes are lost. This sequence of events results in a loss of cache coherency.
Another cache coherency problem relates to determining which cached blocks are still valid (in agreement with a master copy at the server) after rebooting a persistent buffer cache. Where multiple different caching clients (buffer caches) can modify the same primary storage, a cache invalidation technique is employed when a client modifies a block of storage, to let other caching clients know that their copies of that cached block are no longer valid. This is usually done as follows:
First, the client that is modifying a given block writes a new version of the data for that block to its cache, and also notifies the storage server that it has modified that block (the client may or may not send the new data immediately to the server, depending on whether it is a write-through cache or a write-back cache). In response, the storage server will then immediately notify all caching clients that have a copy of that block that their copy is now invalid. This method works correctly while all the caching clients are up and running. However, if the clients are implementing persistent caches, and any client that has that block cached is offline when the modification takes place (i.e., powered down, inactive, off the network, or otherwise out of communication with the server), then some method is needed to ensure that when that client is rebooted, it will not treat its out-of-date copy of the block as valid data.
Another cache coherency problem relates to the use of flash memory. When using flash memory as a caching device, it improves performance significantly to do mostly sequential writes to the cache, because random writes to flash memory are much slower than sequential writes. The advantage of sequential writes is so large for some types of flash memory that it is sometimes preferable to write new data for a cached block to the next sequentially chosen position in the cache, rather than overwriting the older copy of the block (which would entail a non-sequential write).
A disadvantage of doing that, however, is that the cache then contains two or more different versions of the data for that block. This situation reduces the amount of useful data the cache can hold and also introduces a cache coherency problem if the cache is a persistent cache (i.e., if the data in the cache is to be preserved across reboots of the cache). While the cache is in operation, it can use metadata to keep track of which cache location has the latest version of each cached block of storage, ignoring the older versions. But when the persistent cache is rebooted, it needs some way to determine which of the multiple versions of a cached data block is the latest one.